<?php
/*
 * 给定两颗二叉树T1和T2，怎么知道是否T1的某棵子树和T2相等。并返回结果
 */

require_once '../../../class/TreeNode.class.php';
$t1 = new TreeNode(1);
$t1->left = new TreeNode(2);
$t1->right = new TreeNode(3);
$t1->left->left = new TreeNode(4);
$t1->left->right = new TreeNode(5);
$t1->right->left = new TreeNode(6);
$t1->right->right = new TreeNode(7);
$t1->left->left->right = new TreeNode(8);
$t1->left->right->left = new TreeNode(9);

$t2 = new TreeNode(2);
$t2->left = new TreeNode(4);
$t2->left->right = new TreeNode(8);
$t2->right = new TreeNode(5);
$t2->right->left = new TreeNode(9);
$obj = new Middle_Day07_Code_01();
$res = $obj->main($t1, $t2);
var_dump($res);

class Middle_Day07_Code_01
{
    // 将两棵树序列化，如果t2是t1的子树，那么必为子串（KMP算法）
    public function main($t1, $t2)
    {
        $res1 = $res2 = [];
        $this->_serialByPre($t1, $res1);
        $this->_serialByPre($t2, $res2);
        return $this->_getIndexOf($res1, $res2) != -1;
    }

    // 树的序列化
    protected function _serialByPre($head, &$res)
    {
        if ($head == null) {
            $res[] = '#';
        } else {
            $res[] = $head->val;
            $this->_serialByPre($head->left, $res);
            $this->_serialByPre($head->right, $res);
        }
    }

    protected function _getIndexOf($res1, $res2)
    {
        if ($res1 == null || $res2 == null || count($res2) < 1 || count($res1) < count($res2)) {
            return -1;
        }
        $nextArr = $this->_getNextArr($res2);
        $index = 0;
		$mi = 0;
		while ($index < count($res1) && $mi < count($res2)) {
            if ($res1[$index] == $res2[$mi]) {
                $index++;
                $mi++;
            } else if ($nextArr[$mi] == -1) {
                $index++;
            } else {
                $mi = $nextArr[$mi];
            }
        }
		return $mi == count($res2) ? $index - $mi : -1;
    }

    protected function _getNextArr($res)
    {
        $len = count($res);
        if ($len == 1) {
            return [-1];
        }
        $nextArr = array_fill(0, $len, 0);
		$nextArr[0] = -1;
		$nextArr[1] = 0;
		$pos = 2;
		$cn = 0;
		while ($pos < count($nextArr)) {
            if ($res[$pos - 1] == $res[$cn]) {
                $nextArr[$pos++] = ++$cn;
            } else if ($cn > 0) {
                $cn = $nextArr[$cn];
            } else {
                $nextArr[$pos++] = 0;
            }
        }
		return $nextArr;
    }
}